#-----------------------------------[知乎：叶枝黎曼]---------------------------
'''
求关于 x 的同余方程 ax≡1(modb) 的最小正整数解。

输入格式
输入只有一行，包含两个正整数 a,b，用一个空格隔开。

输出格式
输出只有一行，包含一个正整数 x，表示最小正整数解。

输入数据保证一定有解。

数据范围
2≤a,b≤2×109
输入样例：
3 10
输出样例：
7
'''

def exGcd(a,b):
    if b == 0:
        return 1,0,a
    x,y,gcd = exGcd(b,a%b)
    return y, x - a // b * y,gcd


a,b = map(int,input().split())
x,y,gcd = exGcd(a,b)

n = b // gcd
x = x * 1 // gcd

print((x%n + n)%n)
